#include<iostream>
using namespace std;

class MyLinkedList {
public:

	struct Node {
		int val;
		Node *next;
		Node(int val) :val(val), next(NULL) {};
	};
	Node *L;
	int size;
	MyLinkedList() {
		L=new Node(0);
		size = 0;
	}

	int get(int index) {
		if (index < 0||index>=size) return -1;
		Node *r = L->next;
		int start = 0;
		while (index != start) {
			r = r->next;
			start++;
		}
		return r->val;
	}

	void addAtHead(int val) {
		Node *r = new Node(val);
		r->next=L->next;
		L->next = r;
		size++;
	}

	void addAtTail(int val) {
		Node *t = L;
		for (int i = 0; i < size; i++) 
			t = t->next;
		Node *r = new Node(val);
		t->next = r;
		size++;
	}

	void addAtIndex(int index, int val) {
		if (index > size) return;
		else if (index == size) {
			addAtTail(val);
			return;
		}
		else if (index < 0) {
			addAtHead(val);
			return;
		}
		Node *r = new Node(val);
		Node *t = L;
		int start = 0;
		while (start != index) {
			start++;
			t = t->next;
		}
		r->next = t->next;
		t->next = r;
		size++;
	}

	void deleteAtIndex(int index) {
		if (index < 0 || index >= size) return;
		Node *t = L;
		int start = 0;
		while (start != index) {
			start++;
			t = t->next;
		}
		Node *r = t->next;
		t->next = r->next;
		size--;
		delete(r);
	}
};

void main() {
	int index = 1;
	int val = 10;
	MyLinkedList* obj = new MyLinkedList();
	obj->addAtHead(7);
	obj->addAtHead(2);
	obj->addAtHead(1);
	obj->addAtIndex(3, 0);
	obj->deleteAtIndex(2);
	obj->addAtHead(6);
	obj->addAtTail(4);
	int x = obj->get(4);
	obj->addAtHead(4);
	obj->addAtIndex(5, 0);
	obj->addAtHead(6);
	cout << "Done";
}